package Algorithm.dfs;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 200. 岛屿数量 https://leetcode.cn/problems/number-of-islands
 * 题目简述：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 */
public class NumIslands {

    /**
     * 思路：遍历矩阵，遍历到一个1时进行dfs整座岛屿并标记已遍历网格，然后岛屿数增1。dfs遍历时注意遇边界时返回
     * 参考：https://leetcode.cn/problems/number-of-islands/solutions/211211/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/
     */
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0;i < grid.length;i++) {
            for (int j = 0; j < grid[0].length; j++) {
                //若遍历到一个未遍历的岛屿网格，则通过dfs将这座岛屿所有网格全部遍历并标记。岛屿数增1
                if(grid[i][j] == '1') {
                    dfs(i, j, grid);
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 通过dfs遍历网格中的一座岛屿，并将遍历过的岛屿网格标记
     * 0：海洋网格
     * 1：未遍历的岛屿网格
     * 2：已遍历的岛屿网格
     */
    public void dfs(int i, int j, char[][] grid) {
        //越界则返回
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length)
            return;
        //若不是未遍历的岛屿网格则返回
        if (grid[i][j] != '1')
            return;
        //否则将其遍历 标记为2
        grid[i][j] = '2';
        //并dfs遍历上下左右临近网格
        dfs(i-1, j, grid);
        dfs(i+1, j, grid);
        dfs(i, j-1, grid);
        dfs(i, j+1, grid);
    }






    //解法超时
    public int numIslands2(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        boolean[][] checked = new boolean[m][n];
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                if(!checked[i][j] && grid[i][j] == '1') {
                    count++;
                    Deque<Tuple2<Integer, Integer>> checkQueue = new ArrayDeque<>();
                    checkQueue.add(new Tuple2<>(i, j));
                    while (!checkQueue.isEmpty()) {
                        Tuple2<Integer, Integer> t = checkQueue.remove();
                        checked[t._1][t._2] = true;
                        if (t._1 - 1 >= 0 && !checked[t._1 - 1][t._2] && grid[t._1 - 1][t._2] == '1')
                            checkQueue.add(new Tuple2<>(t._1 - 1, t._2));
                        if (t._1 + 1 < m && !checked[t._1 + 1][t._2] && grid[t._1 + 1][t._2] == '1')
                            checkQueue.add(new Tuple2<>(t._1 + 1, t._2));
                        if (t._2 - 1 >= 0 && !checked[t._1][t._2 - 1] && grid[t._1][t._2 - 1] == '1')
                            checkQueue.add(new Tuple2<>(t._1, t._2 - 1));
                        if (t._2 + 1 < n && !checked[t._1][t._2 + 1] && grid[t._1][t._2 + 1] == '1')
                            checkQueue.add(new Tuple2<>(t._1, t._2 + 1));
                    }
                }
            }
        }
        return count;
    }


    class Tuple2<S, T> {
        S _1;
        T _2;

        public Tuple2(S _1, T _2) {
            this._1 = _1;
            this._2 = _2;
        }
    }
}
